#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;
/*HJJ QQ479287006
 *给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//返回p q的祖先节点
//TODO 抓紧练习
TreeNode *lowestCommonAncestor111(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (root == p || root == q || root == nullptr)
        return root;

    TreeNode *left = lowestCommonAncestor111(root->left, p, q);
    TreeNode *right = lowestCommonAncestor111(root->right, p, q);

    if (left && right)
        return root;//说明这个是跟节点 分赛在两边

    if (!left && right) {
        return right;
    } else if (!right && left) {

        return left;
    }

    return nullptr;

}

//非递归方式
//todo 先求根到qp的路径 ， 然后倒叙寻找他们的pq 公共节点。
//获取路径并且逆转
vector<TreeNode *> retTemp;//当时应该就是求这个时候 出现了  问题 然后全局了

//获取路径并且逆转
void getPath(TreeNode *root, TreeNode *ptr, vector<TreeNode *> &ret) {

    if (root == nullptr)
        return;

    retTemp.push_back(root);

    if (root == ptr) {

        reverse(retTemp.begin(), retTemp.end());
        ret = retTemp;
        return;
    }

    getPath(root->left, ptr, ret);
    getPath(root->right, ptr, ret);
    retTemp.pop_back();//注意这里的pop 因为那边不是统一收集的 这边又传来了一个临时变量 否则ret的时候 这个数组Wienull了
}

TreeNode *lowestCommonAncestor1(TreeNode *root, TreeNode *p, TreeNode *q) {
    vector<TreeNode *> ps;
    getPath(root, p, ps);
    retTemp.clear();//这里需要清除 因为是公用全局
    vector<TreeNode *> qs;
    getPath(root, q, qs);

    for (const auto &item : ps) {
        auto iter = find(qs.begin(), qs.end(), item);
        if (iter != qs.end()) {
            return *iter;
        }
    }
    return nullptr;

}